package com.itheima.datastructure.linkedlist;

/**
 * 有序链表去重[1, 2, 3, 3, 4, 4, 5] 删除重复元素[1,2,5]
 */
public class E05Leetcode82 {

    ListNode deleteDuplicates0(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode sentinel = new ListNode(-1, head);
        ListNode pre = sentinel;
        ListNode cur = head;
        while (cur != null && cur.next != null) {

            //当前节点和下一个节点的值相等
            if (cur.val == cur.next.val) {
                //一直找到下一个节点的值不相等的节点
                ListNode notEq = cur.next.next;
                while (notEq != null && cur.val == notEq.val) {
                    //移动notEq
                    notEq = notEq.next;
                    //移动cur
                    cur = cur.next;
                }

                //删除当前及和当前相等的后续节点
                pre.next = notEq;
                //移动cur指针
                cur = notEq;
            } else {
                pre = pre.next;
                cur = cur.next;
            }

        }
        return sentinel.next;
    }


    // 方法1:从当前节点开始，完成去重的链表
    public ListNode deleteDuplicates1(ListNode cur) {
        if (cur == null || cur.next == null) {
            return cur;
        }
        if (cur.val == cur.next.val) {
            //nnext
            ListNode nnext = cur.next.next;
            //直到找到与cur不同的节点
            while (nnext != null && nnext.val == cur.val) {
                nnext = nnext.next;
            }
            return deleteDuplicates1(nnext); // x 就是与 p 取值不同的节点
        } else {
            //更新 cur
            cur.next = deleteDuplicates1(cur.next);
            //返回自身
            return cur;
        }
    }

    /*
        p1 p2 p3
        s, 1, 1, 1, 2, 3, null

        p1 p2    p3
        s, 1, 1, 1, 2, 3, null

        p1 p2       p3
        s, 1, 1, 1, 2, 3, null

        p1 p3
        s, 2, 3, null

        p1 p2 p3
        s, 2, 3, null

           p1 p2 p3
        s, 2, 3, null
     */
    // 方法2
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode s = new ListNode(-1, head);
        ListNode pre = s;
        ListNode cur, next;
        while ((cur = pre.next) != null && (next = cur.next) != null) {

            // 判断当前节点和下一个节点的值是否相等
            if (cur.val == next.val) {
                while ((next = next.next) != null
                        && next.val == cur.val) {
                }
                // p3 找到了不重复的值
                pre.next = next;
            } else {
                pre = pre.next;
            }
        }
        return s.next;
    }

    public static void main(String[] args) {
        ListNode head = ListNode.of(1, 1, 2, 3, 3, 4, 4, 5);
//        ListNode head = ListNode.of(1, 1, 1, 2, 3);
        System.out.println(head);
        System.out.println(new E05Leetcode82().deleteDuplicates0(head));
    }
}
